/**
 * 15. 三数之和
 * 给你一个整数数组 numbs ，判断是否存在三元组 [numbs[i], numbs[j], numbs[k]] 满足 i != j、i != k 且 j != k ，同时还满足 numbs[i] + numbs[j] + numbs[k] == 0 。请
 * 你返回所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 */
pub fn three_sum(numbs: Vec<i32>) -> Vec<Vec<i32>> {
    let mut nu = numbs.clone();
    let mut result: Vec<Vec<i32>> = Vec::new();
    nu.sort();
    for i in 0..nu.len() {
        if nu[i] > 0 {
            return result;
        }
        if i > 0 && nu[i] == nu[i - 1] {
            continue;
        }
        let mut left = i + 1;
        let mut right = nu.len() - 1;
        while left < right {
            let sum = nu[i] + nu[left] + nu[right];
            if sum > 0 {
                right -= 1;
            } else if sum < 0 {
                left += 1;
            } else {
                let ite = vec![nu[i], nu[left], nu[right]];
                result.push(ite);

                while left < right && nu[right] == nu[right - 1] {
                    right -= 1;
                }
                while left < right && nu[left] == nu[left + 1] {
                    left += 1;
                }
                right -= 1;
                left += 1;
            }
        }
    }
    result
}

#[cfg(test)]
mod test {
    use crate::leetcode::three_sum_15::three_sum;

    #[test]
    fn test() {
        let numbs = vec![-1, 0, 1, 2, -1, -4];
        let res = three_sum(numbs);
        println!("{:?}", res);
    }
}
